package HashBuck;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 东莞呵呵
 * Date:2022-07-03
 * Time:17:21
 */
public class HashBuck <K,V>{
    class Node<K,V>{
        public K key;
        public V val;
        public Node<K,V> next;

        public Node(K key, V val) {
            this.key = key;
            this.val = val;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", val=" + val +
                    '}';
        }
    }
    public Node<K,V>[] elem;
    public int useSize;
    public static final double DEFAULT_LOAD_FACTOR=0.75;

    public HashBuck() {
        this.elem = new Node[10];
        this.useSize = 0;
    }
    public void put(K key,V val){
        //1、找到key的位置
        int index=key.hashCode()%this.elem.length;
        //2、判断index位置是否已经有元素。
        Node<K, V> cur=this.elem[index];
        while(cur!=null){
            if (key.equals(cur.key)){
                cur.val=val;
                return;
            }
            cur=cur.next;
        }
        //3、尾插法
        Node<K,V> node=new Node<K,V>(key, val);
        if (this.elem[index]==null){
            this.elem[index]=node;
        }else{
            cur=this.elem[index];
            while (cur.next!=null){
                cur=cur.next;
            }
            cur.next=node;
        }
        this.useSize++;
        //4、插入元素成功之后，检查当前散列表的负载因子
        if(loadFactor()>=DEFAULT_LOAD_FACTOR){
            resize();
        }
    }

    //扩容之后每个元素都要重新哈希
    private void resize(){
        Node<K,V>[] newElem=new Node[this.elem.length*2];
        for (int i = 0; i < this.elem.length; i++) {
            Node<K,V> cur=this.elem[i];
            while(cur!=null){
                int index= cur.key.hashCode()%this.elem.length;
                Node<K,V> newCur=newElem[index];
                if(newCur==null){
                    newElem[index]=cur;
                    cur=cur.next;
                    this.elem[i]=cur;
                    newElem[index].next=null;
                }else {
                    while(newCur.next!=null){
                        newCur=newCur.next;
                    }
                    newCur.next=cur;
                    cur=cur.next;
                    this.elem[i]=cur;
                    newCur.next.next=null;
                }

            }
        }
        this.elem=newElem;
    }

    private double loadFactor(){
        return 1.0*this.useSize/this.elem.length;
    }
    public V get(K key){
        int hash = key.hashCode();
        int index = hash % elem.length;
        Node<K,V> cur = elem[index];
        while (cur != null) {
            if(cur.key.equals(key)) {
                //更新val值
                return cur.val;
            }
            cur = cur.next;
        }
        return null;
    }

    @Override
    public String toString() {
        return "HashBuck{" +
                "elem=" + Arrays.toString(elem) +
                ", useSize=" + useSize +
                '}';
    }
}
